package com.lw.leetcode.stack.b;

import java.util.LinkedList;

/**
 * Created with IntelliJ IDEA.
 * stack
 * 1438. 绝对差不超过限制的最长连续子数组
 *
 * @author liw
 * @version 1.0
 * @date 2021/12/14 21:06
 */
public class LongestSubarray {

    public static void main(String[] args) {
        LongestSubarray test = new LongestSubarray();

        // 2
        int[] arr = {8, 2, 4, 7};
        int k = 4;

        // 4
//        int[] arr =  {10,1,2,4,7,2};
//        int k = 5;

        // 3
//        int[] arr =  {4,2,2,2,4,4,2,2};
//        int k = 0;

        // 6
//        int[] arr =  {2,2,2,4,4,2,5,5,5,5,5,2};
//        int k = 2;

        int i = test.longestSubarray(arr, k);
        System.out.println(i);
    }

    public int longestSubarray(int[] nums, int limit) {
        LinkedList<Integer> a = new LinkedList<>();
        LinkedList<Integer> b = new LinkedList<>();
        int length = nums.length;
        int st = 0;
        int max = -1;
        for (int i = 0; i < length; i++) {
            int num = nums[i];
            while (!a.isEmpty() && a.peekLast() > num) {
                a.pollLast();
            }
            a.addLast(num);
            while (!b.isEmpty() && b.peekLast() < num) {
                b.pollLast();
            }
            b.addLast(num);
            while (!a.isEmpty() && !b.isEmpty() && b.peekFirst() - a.peekFirst() > limit) {
                int value = nums[st];
                if (value == a.peekFirst()) {
                    a.pollFirst();
                }
                if (value == b.peekFirst()) {
                    b.pollFirst();
                }
                st++;
            }
            max = Math.max(max, i - st);
        }
        return max + 1;
    }

}
